package com.tantou.java.structandalgorithm.sort;

import java.util.Arrays;

/**
 * https://www.cnblogs.com/distance66/p/15018207.html
 * 插入排序
 * <p>
 * 基本思想
 * 举个栗子，插入排序的工作方式像许多人排序一手扑克牌。
 * <p>
 * 开始时，我们的左手为空，桌子上有一堆牌。然后，我们每次从桌子的牌堆顶部拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，最终排序完所有牌。
 * <p>
 * 插入排序是指在待排序的元素中，假设前面 n-1 （其中 n>=2）个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第 n 个数的这个序列也是排好顺序的。
 * <p>
 * 按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。
 */
public class InsertSortTest {

    public static void main(String[] args) {
        int[] nums = {2, 5, 6, 4, 3, 7};
        nums = sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static int[] sort(int[] nums) {

        if (nums.length < 1) {
            return nums;
        }

        for (int i = 0; i < nums.length; i++) {
            //外循环，是逐个取出来，然后跟内循环已经排好序的比较，插入到指定位置
            //外循环是待排序，内循环是已排好的

            /**
             * 0...i-1 是有序的，现在要将第i个插入到  0...i-1 里面
             */
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                } else {
                    break;
                }
            }
        }
        return nums;
    }

}
